#include <iostream>

class sequenceList
{
private:
    float* myList;
    int curNumberOfItem;
    int maxCapcity;
    
public:
    /**
    * 顺序表构造函数
    * @param maxSize 顺序表最大容量
    * @param size 目标数组长度
    * @param arr 目标数组
    */
    sequenceList(const int& maxSize, const int& size, float arr[]);

    /**
    * 顺序表析构函数
    */
    ~sequenceList();

    /**
    * 添加元素
    * @param item 添加元素的值
    * @return 是否添加成功
    */
    bool addItem(const float& item);

    /**
    * 插入元素
    * @param index 插入元素的下标
    * @param item 插入元素的值
    * @return 插入是否成功
    */
    bool insertItem(const int& index,const float& item);

    /**
    * 删除元素
    * @param item 目标元素的值
    * @return 被删除元素的下标，找不到返回-1
    */
    int deleteItem(const float& item);

    /**
    * 查找元素（按序号找）
    * @param index 目标元素的下标
    * @param value 将查找到的元素的值存到value中
    * @return 是否查找成功
    */
    bool locate(const int& index, float& value);

    /**
    * 查找元素（按值找）
    * @param item 目标元素的值
    * @return 查找到的元素的下标，找不到返回-1
    */
    int locate(const float& item);

    /**
    * 倒序排列元素（使用原空间）
    */
    void reverse();

    /**
    * 按序输出元素
    */
    void print();
};

class linkList;
class listNode{
    friend class linkList;
    friend void merge(linkList&, linkList&);
private:
    float data;
    listNode* next;
    
public:
    /**
    * 单链表头结点构造函数
    */
    listNode(){next = NULL;}

    /**
    * 单链表结点构造函数
    * @param nodeData 结点元素的值
    * @param succ 后继元素的地址
    */
    listNode(float nodeData, listNode* succ = NULL);

    /**
    * 单链表结点析构函数
    */
    ~listNode();
};

class linkList
{
private:
    listNode* firstNode;
    listNode* curNode;
    listNode* lastNode;

    int listSize;
public:
    /**
    * 单链表构造函数
    */
    linkList();

    /**
    * 单链表构造函数
    * @param size 目标数组长度
    * @param arr 目标数组
    */
    linkList(const int& size, float arr[]);

    /**
    * 单链表析构函数
    */
    ~linkList();

    /**
    * 插入元素（头插法）
    * @param item 插入元素的值
    * @return 是否插入成功
    */
    bool headInsertItem(const float& item);

    /**
    * 插入元素（尾插法）
    * @param item 插入元素的值
    * @return 是否插入成功
    */
    bool tailInsertItem(const float& item);

    /**
    * 插入元素
    * @param index 插入元素的下标
    * @param item 插入元素的值
    * @return 插入元素的下标，错误返回-1
    */
    int insertItem(const int& index, const float& item);

    /**
    * 删除元素
    * @param item 目标元素的值
    * @return 被删除元素的下标，找不到返回-1
    */
    int deleteItem(const float&);

    /**
    * 查找元素（按序号找）
    * @param index 目标元素的下标
    * @param value 将查找到的元素的值存到value中
    * @return 是否查找成功
    */
    bool locate(const int& index, float& value);

    /**
    * 查找元素（按值找）
    * @param item 目标元素的值
    * @return 查找到的元素的下标，找不到返回-1
    */
    int locate(const float&);

    /**
    * 递增排序
    */
    void ascendingOrder();

    /**
    * 倒序排列元素
    */
    void reverse();

    /**
    * 获取链表头结点
    * @return 链表头结点
    */
    listNode* getFirstNode() {
        return firstNode;
    }

    /**
    * 获取链表大小
    * @return 链表大小
    */
    int getListSize() {
        return listSize;
    }

    /**
    * 设置链表第一个数据结点
    * @param node 新的第一个数据结点
    */
    void setFirstDataNode(listNode* node) {
        firstNode->next = node;
    }

    /**
    * 设置链表最后一个结点
    * @param node 新的最后一个结点
    */
    void setLastNode(listNode* node) {
        lastNode = node;
    }

    /**
    * 设置链表大小
    * @param size 新的链表大小
    */
    void setListSize(int size) {
        listSize = size;
    }

    /**
    * 清空所有数据结点（保留头结点）
    */
    void clear();

    /**
    * 按序输出元素
    */
    void print();
    
};

/**
* 将两个单链表归并为一个按元素值递减次序排列的单链表，结果存在list1中
* @param list1 第一个单链表
* @param list2 第二个单链表
*/
void merge(linkList& list1, linkList& list2);